package 回溯;

//给你一个由正整数组成的数组 nums 和一个 正 整数 k 。
//
// 如果 nums 的子集中，任意两个整数的绝对差均不等于 k ，则认为该子数组是一个 美丽 子集。
//
// 返回数组 nums 中 非空 且 美丽 的子集数目。
//
// nums 的子集定义为：可以经由 nums 删除某些元素（也可能不删除）得到的一个数组。只有在删除元素时选择的索引不同的情况下，两个子集才会被视作是不同的
//子集。
//
//
//
// 示例 1：
//
// 输入：nums = [2,4,6], k = 2
//输出：4
//解释：数组 nums 中的美丽子集有：[2], [4], [6], [2, 6] 。
//可以证明数组 [2,4,6] 中只存在 4 个美丽子集。
//
//
// 示例 2：
//
// 输入：nums = [1], k = 1
//输出：1
//解释：数组 nums 中的美丽数组有：[1] 。
//可以证明数组 [1] 中只存在 1 个美丽子集。
//
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 20
// 1 <= nums[i], k <= 1000
//
//
// Related Topics 数组 动态规划 回溯 👍 36 👎 0

import com.google.common.collect.Lists;

import java.util.*;

public class 美丽子集的数目2597 {
	LinkedList<Integer> list = new LinkedList<>();
	Map<Integer, List<Integer>> map = new HashMap<>();
	int total = 0;

	public int beautifulSubsets(int[] nums, int k) {
		Arrays.sort(nums);
		for (int num : nums) {
			List<Integer> valueList = new ArrayList<>(4);
			valueList.add(num - k);
			valueList.add(num + k);
			map.put(num, valueList);
		}
		backTrace(nums,k,nums.length,0);
		return total;
	}

	private void backTrace(int[] nums, int k, int length, int index) {
		//结束条件，到了最后了
		if (length == index) {
			return;
		}
		for (int i = index; i < nums.length; i++) {
			boolean keep = true;
			for (Integer integer : map.get(nums[i])) {
				if (list.contains(integer)) {
					keep = false;
					break;
				}
			}
			if (keep) {
				total = total + 1;
				list.addLast(nums[i]);
				backTrace(nums, k, length, i + 1);
				list.removeLast();
			}
		}
	}
}
